The invention relates generally to elevator group control, and more particularly to optimizing group elevator scheduling and minimizing passenger waiting times.
Group elevator scheduling is a well-known problem in industrial control and operations research with significant practical implications, see Bao et al., xe2x80x9cElevator dispatchers for down-peak traffic,xe2x80x9d Technical Report, University of Massachusetts, Department of Electrical and Computer Engineering, Amherst, Mass., 1994. Given a hall call generated at one of the floors of a building with multiple elevator shafts, the basic objective of elevator group control is to decide which car to use to serve the hall call.
In some elevator systems, the controller assigns a car to the hall call as soon as the call is signaled, and immediately directs the passenger who signaled the hall call to the corresponding shaft by sounding a chime. While in other systems, the chime is sounded when the assigned car arrives at the floor of the hall call.
The traffic patterns of elevator passengers in buildings with multiple elevators varies considerably during certain periods of the day. In an office building, most of the passengers travel from the lobby to the upper floors in the morning, while at the end of the day, most passengers leave the upper floors and travel primarily to the lobby. In a high-rise residential building, the pattern is, of course, the reverse. These traffic patterns are known as up-peak and down-peak.
Up-peak and down-peak pose extraordinary demands on the scheduling processes for the elevator group, because the passenger arrival rate is high, and the traffic pattern is non-uniform. At the same time, these patterns can have a regular probabilistic structure, which could be exploited by car scheduling processes.
For example, free cars can be parked at floors to anticipate future hall calls in a manner that minimizes the usual optimization criterion in elevator group scheduling processes, i.e., the waiting time for future arriving passengers. The idea of moving free cars with the explicit purpose of favorably parking the cars with respect to future hall calls is well known in optimal group elevator scheduling. However, how to do this optimally remains an open question.
Zoning scheduling processes assign a free car to serve all hall calls originating from a fixed set of contiguous floors. Moving the free car to the middle of the zone in advance of hall calls is obviously advantageous to the scheduling process. Another possibility is to use the statistical properties of the traffic pattern in order to dispatch cars to the floors where the cars are most likely needed.
In the case of up-peak pattern, any free car is typically parked at the lobby for the next batch of arriving passengers. This insight has been used for pure up-peak pattern described by Pepyne et al. in xe2x80x9cOptimal dispatching control for elevator systems during up-peak traffic,xe2x80x9d IEEE transactions on control systems technology, 5(6):629-643, 1997. However, pure up-peak traffic, where passengers arrive only at the lobby and only travel upwards, rarely occurs in real settings.
Several parking strategies for free cars are possible. The simplest strategy parks only a single car at a time, as soon as the car becomes free after servicing all previously assigned hall calls. Another strategy tries to maintain a predetermined number of free cars at a particular floor with high arrival intensity, e.g., the lobby in up-peak travel, and parks a free car at that floor only when the number of free cars there falls below a required minimum. However, it is known that this also is a suboptimal strategy.
It is desired to optimize the parking of free elevator cars in elevator group control for both up-peak and down-peak traffic patterns.
The invention provides for optimal parking of free cars in elevator group control so as to anticipate and quickly serve newly arrived passengers and minimize their waiting time. The invention provides a solution for both down-peak and up-peak traffic patterns. By matching the parking of free cars to the arrival rate of passengers, savings in waiting time of up to 80% can be achieved, particularly for down-peak traffic. For the much harder case of the up-peak traffic pattern, the invention models the elevator system as a Markov decision process (MDP) with relatively few aggregated states, and determines an optimal parking strategy by means of dynamic programming on the MDP model.
More particularly, a method controls the distribution of free cars in an elevator system. First, the number of free cars in the elevator system are counted whenever this number changes. At the same time, the arrival/destination rates of passengers at each of the floor is determined. The rates are used to identify up-peak and down-peak traffic patterns. The floors of the building are then assigned to zones. The number of floors in each zone is determined according to the arrival rates, and the free cars are then parked in the zones so that the expected waiting time of the next arriving passenger is minimized.